#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

int knapsackProblem(int limit, vector<vector<int>>& items)
{
  vector<int> line(limit+1, 0);
  vector<vector<int>> arr(items.size()+1, line);
  for(int i = 1; i <= items.size(); ++i)
  {
    for(int j = 1; j <= limit; ++j)
    {
      int value = items[i-1][0];
      int weight = items[i-1][1];
      if(weight > j)
        arr[i][j] = arr[i-1][j];
      else
        arr[i][j] = max(arr[i-1][j-weight]+value, arr[i-1][j]);
    }
  }
  return arr.back().back();
}

int main(int argc, char const *argv[])
{
  vector<vector<int>> items
  {
    {1, 2},
    {4, 3},
    {5, 6},
    {6, 7}
  };
  cout << knapsackProblem(10, items) << endl;
  return 0;
}